Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Implement Trie (Prefix Tree) (medium)

Problem Statement

Design and implement a Trie (also known as a Prefix Tree). A trie is a tree-like data structure that stores a dynamic set of strings, and is particularly useful for searching for words with a given prefix.

Implement the Solution class:

  • Solution() Initializes the object.
  • void insert(word) Inserts word into the trie, making it available for future searches.
  • bool search(word) Checks if the word exists in the trie.
  • bool startsWith(word) Checks if any word in the trie starts with the given prefix.

Examples

  1. Example 1:

    • Input:
      • Trie operations: ["Trie", "insert", "search", "startsWith"]
      • Arguments: [[], ["apple"], ["apple"], ["app"]]
    • Expected Output: [-1, -1, 1, 1]
    • Justification: After inserting "apple", "apple" exists in the Trie. There is also a word that starts with "app", which is "apple".
  2. Example 2:

    • Input:
      • Trie operations: ["Trie", "insert", "search", "startsWith", "search"]
      • Arguments: [[], ["banana"], ["apple"], ["ban"], ["banana"]]
    • Expected Output: [-1, -1, 0, 1, 1]
    • Justification: After inserting "banana", "apple" does not exist in the Trie but a word that starts with "ban", which is "banana", does exist.
  3. Example 3:

    • Input:
      • Trie operations: ["Trie", "insert", "search", "startsWith", "startsWith"]
      • Arguments: [[], ["grape"], ["grape"], ["grap"], ["gr"]]
    • Expected Output: [-1, -1, 1, 1, 1]
    • Justification: After inserting "grape", "grape" exists in the Trie. There are words that start with "grap" and "gr", which is "grape".

Constraints:

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Try it yourself

Try solving this question here:

Java
Saved to Cloud

. . . .
Solution: Combination Sum
Solution: Implement Trie (Prefix Tree)
Mark as Completed

On this page

Problem Statement

Examples

Try it yourself